想验证复杂问题的答案？去“审问”纠缠的量子计算机吧！

可用计算机检验的问题范围扩大了，秘诀正是量子纠缠。

KEVIN HARTNETT

封面：Nick Sullo

Computer Science  计算机科学

假设你得到了一只神奇的黑匣子（oracle），据说它能够揭示关于宇宙最深奥的秘密。在好奇之余，你也会对它半信半疑。如果有什么办法能验证这个黑匣子说的都是真话就好了。

这也是计算机科学一大难题的症结所在。有些问题本身太难了，不知猴年马月才能解开；不过，我们可以轻松地检查答案正确与否。因此，计算机科学家们想要探究的是，在确保答案可验证的前提下，问题到底可以复杂到何种地步？

答案是：复杂得难以想象。

在今年四月发表的一篇论文中，两名计算机科学家证明，这些难解却容易验证答案的问题的数量，远远超出人们先前的认知。他们在文中描述了一种方法，能够检验复杂到几乎无法理解的问题的答案。“这听起来太疯狂了。”加州理工学院的计算机科学家托马斯·韦迪克（Thomas Vidick）评论道。他没有参与到此次的论文中。

这项研究适用于量子计算机——它们依靠量子力学不合常识的原理实现计算功能。虽然目前还没有成熟的量子计算机，但它在将来可能会掀起计算革命。

这项新研究的成果让我们能够对付开头提到的那只强大的黑匣子。即使它声称解出的问题让你无计可施，我们也有办法确保它没有撒谎。

直到宇宙尽头

如果解出一个问题的答案需要很长时间，验证既有答案的正确性却很容易，我们称这样的问题“难解易验”。

举个例子：假设有人给你一张图（graph），图上画着一堆由线段（边）连接起来的点（顶点），问你是否可能只用三种颜色给顶点着色，而每对相连的顶点颜色都不同。

在三着色图中，每个顶点都被涂成三种颜色中的一种颜色，和它相邻的顶点则是其他颜色。

—

5W Infographics for Quanta Magazine

这个“三着色问题”很难解答。一般来说，随着原图边数（size）增加，找到着色方案（或者判定无解）的时间呈指数级增长。也就是说，假如解出一个有20个顶点的图需要3^20纳秒（几秒钟），那么有60个顶点的图就需要大约3^60纳秒，相当于宇宙年龄的100倍左右。

不过，假如有人声称他涂好色了，检验是否正确花不了多久。你只需要挨个检查图上的顶点，确保每对相连的顶点不同色就可以。随着边数增加，检查答案所需时间缓慢增长——准确地说，属于多项式级（polynomial）增长。因此，计算机检查有60个顶点的三着色图，并不会比20个顶点的图多费太多时间。

“对于符合条件的三着色图，我们很容易验证。”麻省理工学院的物理学家约翰·莱特（John Wright）说道。他和加州理工学院的阿南德·纳塔拉江（Anand Natarajan）共同撰写了此次的论文。

早在上世纪70年代，计算机科学家们就为这类“难解易验”问题起了名字，叫做“NP”，即非确定多项式时间（nondeterministic polynomial time）。从那时起，NP类问题一直是计算机科学领域的热点。计算机科学家们尤其好奇的是，如果检验者（verifier）有新的验证方法，NP问题的范围是否会变化。

问对问题

在纳塔拉江和莱特的研究之前，验证力已经有两次飞跃式的提升。

为了解释第一次飞跃，让我们先假设你是色盲。有人在你面前的桌子上放了两个色块，而你需要判断这两个色块是否同色。你无能为力。更糟糕的是，你也没办法验证别人的答案。

好在你可以询问一个我们称之为“证明者”（prover）的人。假设证明者告诉你两个色块不同色。于是你把其中一个色块标记成“色块A”，另一个叫“色块B”，在背后把色块打乱，然后让证明者辨认哪个是色块A。

如果这两个色块的确不同色，问题就变得非常简单。比如，要是色块A是红色，证明者只需要指出红色的色块，每次都能正确辨认出色块A。

反之，如果证明者撒谎，两个色块其实颜色一样，证明者就只能猜测哪个是色块A。他猜对的概率只有50%。因此，你可以反复测试证明者能否正确辨认色块A，来验证他最初的答案是否正确。

 “检验者可以向证明者提问，”莱特说，“通过反复对话，检验者或许能更确信证明者的答案是正确的。”

Anand Natarajan（左）和John Wright在他们的新研究中利用了量子力学。

—

David Sella (Natarajan); Soya Park (Wright)

1985年，三位计算机科学家证明了这种交互式证明可以用来验证比NP问题更复杂的难题。被称为IP的新问题类别就此诞生。IP指的是交互式多项式时间（interactive polynomial time）。这种用来检验两个色块颜色异同的方法，也可以用来检验其他更加复杂的问题的答案。

依然是80年代，科学家们迎来了第二次大飞跃。它和警方审讯的原理很像。假设你面前有两个你认定的犯罪嫌疑人，你当然不会同时审问这两个人。你会他们安排在不同的房间单独审讯，然后比对证词。比起只盘问一个嫌疑人，这样你更能逼近案件的真相。

“（两个嫌疑人）无法串通证词，达成一致口径，原因很简单——他们不知道对方准备说什么。”莱特说道。

1988年，四位计算机科学家证明了新的理论：通过单独“审问”两台独立解决同一个问题的计算机，你可以验证的问题范围更大，而IP只是其中一小部分。这类难题被称为MIP，即多证明者交互式证明（multi-prover interactive proofs）。

举个例子，采用多证明者交互式方法，我们可以验证一系列边数增长速度比NP类快得多的三着色问题的答案。NP类图的顶点数从1开始逐个增加，是线性增长，所以这些图的边数和验证相应答案所需的时间始终保持相称。但是，MIP类图的顶点数呈指数型增长，也就是从2^1到2^2，再到2^3，以此类推。

结果，图变得巨大，甚至超过了用来检验答案的计算机的内存，因此计算机不可能靠挨个检查图中的顶点来检验。不过我们可以分别向两个证明者提出相互关联的问题，依然能验证三着色问题的解答。

MIP问题检验者的内存足以判断图中任意两个顶点之间是否相连。检验者接着可以要求每个证明者说出两个相连顶点中一个顶点的颜色，并交叉参考证明者的答案，确保着色正确。

 “难解易验”问题的范围从NP扩展到IP，又扩展到MIP，靠的是经典计算机。量子计算机的工作原理完全不同。数十年来，我们一直不清楚量子计算机将如何改变局面——它们会提高验证解答的难度，还是降低验证解答的难度？

答案在纳塔拉江和莱特的新成果中。

量子戏法

量子计算机的计算依靠操纵量子比特，即量子位（qubits）。量子位的奇特之处在于，它们能够互相纠缠。当两个量子位或两个量子位系统处于纠缠态，它们彼此的物理性质会以特定的方式相互影响。

纳塔拉江和莱特在新研究中考察了这样的方案：使用两台共享纠缠量子位的量子计算机。

—James O’Brien for Quanta Magazine 

乍一看，这个设计对检验答案只会帮倒忙。多证明者交互式证明的威力正在于，我们能分别向两个证明者提问并核对答案。如果证明者的答案一致，那它们很可能就是正确答案。但是有了共享的纠缠态，两个证明者似乎就更可能给出一致的错误答案。

事实上，2003年首次提出使用两台纠缠的量子计算机的方案时，计算机科学家们假定量子纠缠只会削弱验证力。“包括我本人，所有人都想当然地认为，这样一来证明者就更强大了，”韦迪克说，“它们可以利用量子纠缠来关联答案。”

尽管第一反应是悲观的，韦迪克还是花了好几年试图证明量子纠缠不会帮倒忙。2012年，他和伊藤刚志（Tsuyoshi Ito）终于证明了纠缠的量子计算机依然可能检验所有MIP类问题的答案。

而纳塔拉江和莱特现在进一步证明了，量子纠缠不仅不会帮倒忙，而且我们可以借助它检验更广泛的问题的答案，这是没有量子纠缠就做不到的。检验者可以将纠缠的量子计算机之间的联系转化为自身优势。

让我们回忆一下在MIP问题中，如何验证边数指数增长的三着色问题的答案：检验者的内存不够储存整张图，但足以识别两个相连的顶点，并询问证明者这些顶点的颜色。

纳塔拉江和莱特关心的这类问题被称为NEEXP，即非确定双重指数级时间（nondeterministic doubly exponential time）。NEEXP类图的边数增速比MIP类还要快，它们以“双重指数级”速率增长。顶点数不以2的次方级增长（即2^1，2^2，2^3，2^4等），而是2的次方的次方级，即2^2^1，2^2^2，2^2^3，2^2^4等。因此，图很快变得非常非常大，检验者甚至不可能识别任何一对相连的顶点。

纳塔拉江说：“标记一个顶点就需要2的n次方个比特，比证明者的工作记忆所含的比特数大了指数倍。”

但是纳塔拉江和莱特证明的是，即使检验者不清楚该就哪个顶点向证明者提问，依然可以验证一个有双重指数级边数的三着色图是否正确。原因是，你可以让证明者向自己提问。

在计算机科学家们看来，让电脑审问自己的答案无异于让嫌疑犯审讯自己，这个提议无疑是愚蠢的。纳塔拉江和莱特却证明了事实恰恰相反。关键在于量子纠缠。

 “纠缠态好比一个共享资源，”莱特说，“我们整个证明协议（protocol）就是要弄明白，如何用这个共享资源来生成相关联的问题。”

如果若干量子计算机相互纠缠，那么它们对顶点的选择就会相互关联，从而产生恰好可以验证着色的一组问题。

另一方面，检验者不希望两台量子计算机缠绕得过于紧密，否则它们的回答也会是相关的（好比两个嫌疑人串供）。量子的另一种特性可以打消这一顾虑。在量子力学中，不确定性原理确保我们不可能同时得知一个粒子的位置和动量——测量其中一个性质，就破坏了关于另一个性质的信息。不确定性原理严格地限制了我们对一个量子体系的任意两个“互补”性质的了解。

纳塔拉江和莱特的成果正是利用了这一原理。他们让两台量子计算机分别测量互补的顶点来算出顶点的颜色。每台计算机只算它自己的顶点的颜色，于是关于另一台计算机算的顶点的信息就被销毁了。换句话说，量子纠缠使得计算机能够生成相关联的问题，但不确定性原理防止了它们串通答案。

 “你需要强迫证明者忘记，这正是他们论文的核心思想。”韦迪克说，“他们迫使证明者通过测量行为抹去一些信息。”

这项研究大大提高了我们确信有可能掌握的知识的下限，其意义几乎触及人类存在的本质问题。过去，面对一个NEEXP类问题的答案，我们除了盲目相信外别无选择。纳塔拉江和莱特突破了这一限制，使得检验更广泛的计算问题的答案成为可能。

基于他们的成就，我们还不知道验证力的极限究竟在哪。

 “或许还有很大增长空间，”佐治亚理工学院的计算机科学家兰斯·福特那（Lance Fortnow）说，“他们没有排除更进一步的可能。”

翻译：amecolli

审校：有耳

编辑：酸酸

https://www.quantamagazine.org/computer-scientists-expand-the-frontier-of-verifiable-knowledge-20190523/

Kevin Hartnett

《Quanta》杂志资深作家，负责数学和计算机科学。

····

← 往期回顾（滑动有惊喜） →

深读

1

2

3

4

Messages from the unseen world_

神经现实| 大脑 心智 认知

神经现实是公益的科学传播组织，专注于神经科学、认知科学、神经病学和精神病学等领域的深度报道和前沿解读。点击“阅读原文”，进一步了解我们。